package com.lun.swordtowardoffer2.c15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class OpenLock {

	public int openLock(String[] deadends, String target) {
		Set<String> dead = new HashSet<>(Arrays.asList(deadends));
		Set<String> visited = new HashSet<>();
		
		String init = "0000";
		if(dead.contains(init) || dead.contains(target)) {
			return -1;
		}
		
		Queue<String> queue1 = new LinkedList<>(); 
		Queue<String> queue2 = new LinkedList<>(); 
		
		int steps = 0;
		
		queue1.offer(init);
		visited.add(init);
		while(!queue1.isEmpty()) {
			String cur = queue1.poll();
			
			if(cur.equals(target)) {
				return steps;
			}
			
			List<String> neighbors = getNeighbors(cur);
			for(String neighbor : neighbors) {
				
				if(!dead.contains(neighbor) && !visited.contains(neighbor)) {
					visited.add(neighbor);
					queue2.offer(neighbor);
				}
			}
			
			if(queue1.isEmpty()) {
				steps++;
				Queue<String> temp = queue1;
				queue1 = queue2;
				queue2 = temp;
				
			}
			
		}
		
		return -1;
	}

	private List<String> getNeighbors(String cur) {
		
		List<String> result = new ArrayList<>();
		
		for(int i = 0; i < cur.length(); i++) {
			char ch = cur.charAt(i);
			
			char newCh = ch == '0' ? '9' : (char)(ch - 1);
			StringBuilder sb = new StringBuilder(cur);
			sb.setCharAt(i, newCh);
			result.add(sb.toString());
			
			newCh = ch == '9' ? '0' : (char)(ch + 1);
			sb.setCharAt(i, newCh);
			result.add(sb.toString());
		}
		
		return result;
	}
	
}
